/*************************************
 *                                   *
 *         Alex & Umit               *
 *                                   *
 ************************************/

public class BinSearchTree
{
    private BinTree bt;
    private int sumGet = 0;
    private int sumPut = 0;

    //heeft een lege BinSearchTree gemaakt die 1 externe knoop bevat met waarde null
    public BinSearchTree()
    {
        bt = new BinTree();
        bt.addRoot(new Item(null, null));
    }

    //wrapper methode om de volgende get methode aan te roepen
    public Position get(String key)
    {
        return get(key, bt.root());
    }

    //retourneert Position van het 1e item vanaf p dat key bevat.
    //doorloopt recursief de binaire zoekboom
    public Position get(String key, Position p)
    {
        sumGet++;
        int cmp;

        if (bt.isExternal(p))
            return p;

        else
            cmp = key.compareTo(positionToItem(p).key());
        
        Position tmp;

        // found node to insert in
        if (cmp == 0)
            return p;

        // search left
        if (cmp < 0)
            tmp = bt.leftChild(p);

        // search right
        else
            tmp = bt.rightChild(p);
            

        return get(key, tmp);
    }

    //heeft item (key,element) aan een externe knoop toegevoegd, 
	//aan deze (nu interne) knoop zijn twee nieuwe externe knopen toegevoegd
    public void put(String key, Object o)
    {
        sumPut++;
        Item item = new Item(key, o);
        Item emptyItem = new Item(null, null);

        Position p = get(key);

        if (positionToItem(p).key() == null)
        {
            TNode node = bt.toTNode(p);

            node.setElem(item);
            node.setLeft(new TNode(emptyItem, node, null, null));
            node.setRight(new TNode(emptyItem, node, null, null));
            return;
        }
        
        TNode node = bt.toTNode(p);
        

        if (bt.isInternal(p))
        {
            node.setElem(item);
            return;
        }
    }

    //drukt de waarden van sumPut en sumGet af
    public void tellingen()
    {
        System.out.printf("sumGet: %d, sumPut: %d\n", sumGet, sumPut);
    }

    //hulpmethode, converteert een Position naar een Item
    protected Item toItem(Object p)
    {
        if (p instanceof Item)
            return (Item) p;
        else
            throw new AssertionError();
    }

 	//hulpmethode, converteert een Position naar een Item
    public Item positionToItem(Object p)
    {
        if (p instanceof Position)
        {
            if (bt.toTNode((Position) p).element() instanceof Item)
            {
                return (Item) bt.toTNode((Position) p).element();
            }
        }

        throw new AssertionError();
    }
}
